package LeetCode;

import sun.reflect.generics.tree.Tree;

public class DeleteTreeNode {

    public TreeNode deleteNode1(TreeNode root, int value){
        if(root == null) return root;
        if(root.val == value){
            if(root.left == null) return root.right;
            else if(root.right == null) return root.left;
            else{
                TreeNode cur = root.right;
                while(cur.left != null) cur = cur.left;
                cur.left = root.left;
                root = root.right;
                return root;
            }
        }
        if(root.val > value) return root.left = deleteNode1(root.left, value);
        if(root.val < value) return root.right = deleteNode1(root.right, value);
        return root;
    }

    public TreeNode deleteNode(TreeNode root, int value) {
        if (root == null) {
            return root;
        }
        TreeNode p = null;
        TreeNode t = root;
        while (t != null) {
            if (t.val > value) {
                p = t;
                t = t.left;
            } else if (t.val < value) {
                p = t;
                t = t.right;
            } else {
                // 无左右子树
                if (t.left == null && t.right == null) {
                    if (p.val > t.val) {
                        p.left = null;
                    } else {
                        p.right = null;
                    }
                    return root;
                } else if (t.left == null && t.right != null) {
                    if (p.val > t.val) {
                        p.left = null;
                        p.left = t.right;
                    } else {
                        p.right = null;
                        p.right = t.right;
                    }
                    return root;
                } else if (t.left != null && t.right == null) {
                    if (p.val > t.val) {
                        p.left = null;
                        p.left = t.left;
                    } else {
                        p.right = null;
                        p.right = t.left;
                    }
                    return root;
                } else {
                    TreeNode temp = t.right;
                    while (temp.left != null) {
                        temp = temp.left;
                    }
                    temp.left = t.left;
                    if (p.val > t.val) {
                        p.left = t.right;
                        t = null;
                    } else {
                        p.right = t.right;
                        t = null;
                    }
                    return root;
                }

            }
        }
        return root;
    }
}

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int value){
        this.val = value;
    }
}
